A tweakable block cipher refers to a block cipher that has an adjusting value called “tweak” in addition to input/output (plaintext, cipher text, and key) of a normal block cipher.
In a tweakable block cipher, it is required that, even if a tweak and an input are known to an attacker, the outputs of two block ciphers with different tweaks appear to the attacker the random values that are independent to each other. A tweakable block cipher is said to be secure when this requirement is satisfied.
Although some block ciphers that have an auxiliary input similar to a tweak have been proposed, the strict requirements for security have not been defined.
The formal definition of a tweakable block cipher was first established in Non-Patent Document 1.
In Non-Patent Document 1 shows that a theoretically secure tweakable block cipher may be obtained as a mode of operation of a normal block cipher (hereinafter abbreviated simply to “mode”), that is, as a conversion using a block cipher as a black box.
The theoretical security mentioned above means that the security of a tweakable block cipher, obtained as a mode of a block cipher, is ensured by the security of the underlying block cipher, that is, the security of the obtained tweakable block cipher is ensured as long as a secure block cipher is used.
In addition, two types of security definition are:
(I) Security required when an attacker can make a chosen plaintext attack (chosen-plaintext attack, called “CPA”) only
(II) Security required when an attacker can combine a chosen-plaintext attack and a chosen-ciphertext attack (chosen-ciphertext attack, called “CCA”)
(I) is called “CPA-security” and (II) is called “CPA/CCA-security”.
A secure tweakable block cipher is known as a key technology for implementing a sophisticated encryption function.
For example, Non-Patent Document 3 points out the following:                The use of a tweakable block cipher, which provides CPA/CCA-security, can implement a significantly efficient authenticated-encryption.        The use of a tweakable block cipher, which provides CPA-security, can implement an efficient, parallelable message authentication code.        
It is also known that a tweakable block cipher, which provides CPA/CCA-security, is a technology required for a storage encryption such as a disk sector encryption.
In this specification, the mode proposed by Non-Patent Document 1 is called an “LRW mode”. FIG. 7 is a diagram showing the LRW mode.
In the LRW mode, not only a block cipher but also a keyed function f(K, *) is required.
When the security parameter assumes a value of e (e is greater than or equal to 0 and is less than or equal to 1), f(K, *) has the property that, for any c, x, and x′ (x and x′ are different), the probability Pr[f(K, x)+f(K, x′)=c] is less than or equal to e.
In the description above, + represents the exclusive OR.
f(K, *), which has this property, is said to be “e-almost XOR universal”, or “e-AXU” for short.
An e-AXU function is a kind of universal hash functions. An e-AXU function can be implemented by a polynomial operation in the finite field or by the method proposed in Non-Patent Document 2.
They are several times faster than a general block cipher in a specific installation environment.
However, an e-AXU function, which can be implemented in any computer environment and is faster than a block cipher, is not known.
So, the problem is that an e-AXU function is efficient only in an environment where the e-AXU function can be installed for faster operation.
Another problem is that, because two parts—block cipher and e-AXU function—are installed, the program size is generally larger as when only a block cipher is used.
On the other hand, the XEX mode described in Non-Patent Document 3 is also known as a tweakable block cipher that uses only a block cipher. FIG. 8A shows the XEX mode (XEX construction).
In FIG. 8A, mu1 represents the multiplication operation * in the finite field where b is the base and tweak2 is the exponent.
That is, the offset isb^{tweak2}*E(K1,tweak1)
The advantage of this offset is that, when tweak2 is incremented, that is, when one is added to the immediately preceding value of tweak2, the computation can be carried out simply by one bit-shift operation and one exclusive OR operation of a constant.
That is, the offset calculation can be carried out much quicker than the encryption of a block cipher, with the result that the encryption of one block requires only the computation amount for encrypting about one block via a block cipher.
However, because a tweak at a particular point in time is generated only by incrementing the immediately preceding tweak, the XEX mode is applicable to the authenticated encryption but is not suitable for some applications such as the storage encryption.
The authenticated encryption, which uses a mode similar to the XEX mode, is described in Non-Patent Document 1 as the OCB mode. The authenticated encryption that uses the XEX mode itself is described in Non-Patent Document 3 as the OCB1 mode.
On the other hand, because the e-AXU function usually uses about the same amount of calculation for any input to generate the output, the LRW mode usually has not the restrictions involved in the XEX mode described above.
This problem can formally be solved by fixing tweak1 to a constant and treating only tweak2 as the tweak in FIG. 8(A). However, doing so, in turn, requires the computation amount of one block encryption for the offset calculation.
This means that the XEX mode in this case requires the computation amount, comparable to the computation amount of encrypting two blocks via a block cipher, for encrypting one-block.
Both the LRW mode and the XEX mode provide CPA/CCA-security. However, if the second exclusive OR operation via the offset is omitted in the LRW mode and the XEX mode, the obtained mode is a mode that provides CPA-security only.
Although CPA-security is weaker in the concept of security, it is known that CPA security is sufficient in several applications as described above.
In Non-Patent Document 3, the mode, in which the second exclusive OR operation via the offset is omitted in the XEX mode, is defined as the XE mode. FIG. 8B shows the XE mode (XE construction).
Non-Patent Document 1: Moses Liskov, Ronald L. Rivest, David Wagner: Tweakable Block Ciphers. Advanced in Cryptology—CRYPTO 2002, 22nd Annual International Cryptology Conference, Santa Barbara, Calif., USA, Aug. 18-22, 2002, Proceedings. Lecture Notes in Computer Science 2442 Springer 2002, pp. 31-46.
Non-Patent Document 2: S. Halevi and H. Krawczyk, MMH: Software Message Authentication in the G bit/second rates, Fast Software Encryption, 4th International Workshop, FSE '97, Lecture Notes in Computer Science; Vol. 1267, Feb. 1997
Non-Patent Document 3: Phillip Rogaway: Efficient Instantiations of Tweakable Blockciphers and Refinements to Modes OCB and PMAC. Advances in Cryptology—ASIACRYPT 2004, 10th International Conference on the Theory and Application of Cryptology and Information Security, Jeju Island, Korea, Dec. 5-9, 2004, Proceedings. Lecture Notes in Computer Science 3329 Springer 2004, pp. 16-31
Non-Patent Document 4: J. Daemen and V. Rijmen, AES Proposal: Rijndael, AES submission, 1998. Internet<URL:http://csrc.nist.gov/CryptoToolkit/aes/rijndael/Rijndael.pdf>
Non-Patent Document 5: S. Park, S. H. Sung, S. Lee, and J. Lim, Improving the Upper Bound on the Maximum Differential and the Maximum Linear Hull Probability for SPN Structure and AES, International Workshop, FSE 2003, Lecture Notes in Computer Science; Vol. 2887, Feb. 2003
Patent Document 1: U.S. Pat. No. 7,046,802 Specification
The disclosures of Non-Patent Documents 1-5 and Patent Document 1 given above are hereby incorporated in their entirety into this specification.
The methods described above have the following problems (according to the result of analysis made by the inventor).
The conventional XEX mode and XE mode, which perform tweakable block ciphers using only a block cipher, have one of the following problems.                The computation amount of one-block encryption is required for updating a tweak.        A tweak can be update only incrementally.        
In addition, the installation environment of the LRW mode that combines a block cipher and the e-AXU function is limited. This is because an e-AXU function that runs fast in all environments is not known. Even if there is an environment in which the mode can be installed, the program size becomes large because both a block cipher and the e-AXU function are installed.
Accordingly, it is an object of the present invention to provide a tweakable block cipher apparatus, method, and program that combine a block cipher with a part of the block cipher to make it possible to update a tweak in any desired way with the amount of computation smaller than that required for one-block encryption and, at the same time, ensure efficiency in the memory amount used for pre-processing and provide theoretical security.
The invention disclosed by this application generally has the following construction.
A first tweakable block cipher apparatus of the present invention comprises input means that receives a pair of a plaintext and a tweak; offset calculation means that calculates a sum of a value, which is generated by encrypting a fixed plaintext using a block cipher, and the tweak and encrypts the result using a partial block cipher to output an offset; internal encryption means that calculates a sum of the offset and the plaintext, encrypts the sum using the block cipher, calculates a sum of the result and the offset, and outputs the sum as a ciphertext; and output means that outputs the ciphertext.
A second tweakable block cipher apparatus of the present invention comprises input means that receives a pair of a plaintext and a tweak; offset calculation means that calculates a sum of a value, which is generated by encrypting a fixed plaintext using a block cipher, and the tweak and encrypts the result using a partial block cipher to output an offset; internal encryption means that calculates a sum of the offset and the plaintext, encrypts the sum using the block cipher, and outputs the encrypted sum as a ciphertext; and output means that outputs the ciphertext.
A third tweakable block cipher apparatus of the present invention is the first or second tweakable block cipher apparatus wherein the block cipher used by the internal encryption means and the offset calculation means is AES (Advanced Encryption Standard) and the partial block cipher used by the offset calculation means is an iteration of four rounds of a round function of AES.
A fourth tweakable block cipher apparatus of the present invention is the first or second tweakable block cipher apparatus wherein the block cipher and processing using a round function of the block cipher are used.
A first program of the present invention causes a computer, which configures a tweakable block cipher apparatus, to execute:
input processing that receives a pair of a plaintext and a tweak from an input device;
offset calculation processing that calculates a sum of a value, which is generated by encrypting a predetermined fixed plaintext using a block cipher, and the tweak and encrypts the result using a partial block cipher to output an offset;
internal encryption processing that calculates a sum of the offset and the plaintext, encrypts the sum using the block cipher, calculates a sum of the result and the offset, and outputs the sum as a ciphertext; and
output processing that outputs the ciphertext from an output device.
A second program of the present invention causes a computer, which configures a tweakable block cipher apparatus, to execute:
input processing that receives a pair of a plaintext and a tweak from an input device;
offset calculation processing that calculates a sum of a value, which is generated by encrypting a fixed plaintext using a block cipher, and the tweak and encrypts the result using a partial block cipher to output an offset;
internal encryption processing that calculates a sum of the offset and the plaintext, encrypts the sum using the block cipher, and outputs the encrypted sum as a ciphertext; and
output processing that outputs the ciphertext from an output device.
In a third program of the present invention, the block cipher used by the internal encryption processing and the offset calculation processing is AES and the partial block cipher used by the offset calculation processing is an iteration of four rounds of a round function of AES.
In a fourth program of the present invention, the block cipher and processing using a round function of the block cipher are used.
A first method of the present invention is a tweakable block cipher method executed by a computer, comprising:
an input step of receiving a pair of a plaintext and a tweak from an input device;
an offset calculation step of calculating a sum of a value, which is generated by encrypting a predetermined fixed plaintext using a block cipher, and the tweak and encrypting the result using a partial block cipher to output an offset;
an internal encryption step of calculating a sum of the offset and the plaintext, encrypting the sum using the block cipher, calculating a sum of the result and the offset, and outputing the sum as a ciphertext; and
an output step of outputting the ciphertext from an output device.
A second method of the present invention is a tweakable block cipher method executed by a computer, comprising:
an input step of receiving a pair of a plaintext and a tweak from an input device;
an offset calculation step of calculating a sum of a value, which is generated by encrypting a fixed plaintext using a block cipher, and the tweak and encrypting the result using a partial block cipher to output an offset;
an internal encryption step of calculating a sum of the offset and the plaintext, encrypting the sum using the block cipher, and outputting the encrypted sum as a ciphertext; and
an output step of outputting the ciphertext from an output device.
In a third method of the present invention, the block cipher used by the internal encryption step and the offset calculation step is AES and the partial block cipher used by the offset calculation step is an iteration of four rounds of a round function of AES.
In a fourth method of the present invention, the block cipher and processing using a round function of the block cipher are used.
A fifth tweakable block cipher apparatus of the present invention comprises input means that receives a pair of a plaintext and a tweak; offset calculation means that calculates a sum of a value, which is generated by encrypting a fixed plaintext using a block cipher, and the tweak and encrypts the result using a partial block cipher to output an offset; internal encryption means that determines whether a result, which is generated by encrypting a sum of the offset and the plaintext using the block cipher, is output as a ciphertext or a sum of a result, which is generated by the encryption using the block cipher, and the offset is output as a ciphertext according to a value of the tweak.
A fifth program of the present invention causes a computer, which configures a tweakable block cipher apparatus, to execute:
input processing that receives a pair of a plaintext and a tweak from an input device;
offset calculation processing that calculates a sum of a value, which is generated by encrypting a predetermined fixed plaintext using a block cipher, and the tweak and encrypts the result using a partial block cipher to output an offset;
internal encryption processing that determines whether a result, which is generated by encrypting a sum of the offset and the plaintext using the block cipher, is output as a ciphertext or a sum of a result, which is generated by the encryption using the block cipher, and the offset is output as a ciphertext according to a value of the tweak; and
output processing that outputs the ciphertext from an output device.
A fifth method of the present invention is a tweakable block cipher method executed by a computer, comprising:
an input step of receiving a pair of a plaintext and a tweak from an input device;
an offset calculation step of calculating a sum of a value, which is generated by encrypting a fixed plaintext using a block cipher, and the tweak and encrypting the result using a partial block cipher to output an offset;
internal encryption step of determining whether a result, which is generated by encrypting a sum of the offset and the plaintext using the block cipher, is output as a ciphertext or a sum of a result, which is generated by the encryption using the block cipher, and the offset is output as a ciphertext according to a value of the tweak; and
an output step of outputting the ciphertext from an output device.
A first effect of the present invention is that the program size is smaller than that of the LRW mode in which a generally-known algebraic e-AXU function is used.
The reason is that, in the present invention, a part of a block cipher is combined with the block cipher itself instead of using the e-AXU function required in the LRW mode. The other operations required in the present invention are only very simple functions such as an exclusive OR. Therefore, the present invention may substantially be implemented by a block cipher only.
A second effect of the present invention is that a tweak, which may be updated only in a limited way in the XEX mode, may be updated speedily in any desired way.
The reason is that the present invention is configured such that only a part of the block cipher processing is required for updating a tweak and calculating a new offset. The present invention allows a constant plaintext, which must also be encrypted, to be calculated in advance and stored in the memory, thus eliminating the need for the calculation when the tweak is updated.
A third effect of the present invention is that, when the present invention is applied to a known block cipher, the theoretical security comparable to that of the conventional mode can be provided depending upon a part of a block cipher that is used.
The reason is that it can be proved that the present invention provides theoretical security when the maximum average of differential probability of a part of a block cipher used in the present invention and some kind of differential probability related to it are sufficiently low.